package br.ufrj.dcc.org2.binaria;

import java.util.*;
public class HashTable {
	private DataItem[] hashArray; // array de data items
	private int arraySize;
	private DataItem nonItem; // para itens apagados 
	
	private int rootKey[];
	private int hashValTemp[];
	private int rootKeyMove[];

	public HashTable(int size) // construtor
	{
		arraySize = size;
		hashArray = new DataItem[arraySize];
		nonItem = new DataItem(-1); // chave do item deletado eh -1
	}

	public void displayTable() {
		System.out.print("Tabela: ");
		for (int j = 0; j < arraySize; j++) {
			if (hashArray[j] != null)
				System.out.print(hashArray[j].getKey() + " ");
			else
				System.out.print("** ");
		}
		System.out.println("");
	}

	public int hashFunc(int key) {
		return key % arraySize; // funcao de hash 
	}

	// TODO: Quando a tabela esta cheia, o loop do while se torna infinito! Arrumar isso... 
	public void insert(DataItem item) // insere um item
	// (assume q a tabela nao esta lotada)
	{
		int key = item.getKey(); // extrai chave
		int hashVal = hashFunc(key); // hasheia a chave

		// ate achar espaco vazio ou item coalescido (marcado com -1),		
		
		binInsert(key, hashVal, item);
	}
	
	private void binInsert(int key, int hashVal, DataItem item) {
		
		if (hashArray[hashVal] == null || hashArray[hashVal].getKey() == -1) { // espaco vazio
			hashArray[hashVal] = item; // insere item
			return;
		} else {
			binInsertMove(key, hashVal, item, 0);
			return;
		}	
	}

	
	private void binInsertMove(int key, int hashVal, DataItem item, int level) {
		++level;
		
		int hashValCont = hashFuncCont(key) + hashVal;
		hashValCont %= arraySize;		
		
		int hashValMove = hashFuncCont(hashArray[hashVal].getKey()) + hashVal;
		hashValMove %= arraySize;
		
		//rootKey[level] = key;
		//hashValTemp[level] = hashVal;
		//rootKeyMove[level] = hashArray[hashVal].getKey();
		
		if (hashArray[hashValCont] == null || hashArray[hashValCont].getKey() == -1) { // esquerda vazio?
			//vazio, insere, sem mover
			hashArray[hashValCont] = item;
			return;
		}  else if (hashArray[hashValMove] == null || hashArray[hashValMove].getKey() == -1) { // direita vazio?
			//vazio, insere
			hashArray[hashValMove] = hashArray[hashVal];
			hashArray[hashVal] = item;						
			return;
		} else {
			//for (int i = 0; i < level*2; i++){
			if (level < arraySize) // Evita StackOverflow
				binInsertMove(key, hashValMove, item, level);
			//}			
			return;
		}
	}

	private int hashFuncCont(int key) {
		return (key/arraySize) % arraySize;
	}

	public DataItem delete(int key) // deleta um DataItem
	{
		int hashVal = hashFunc(key); // hasheia a chave

		while (hashArray[hashVal] != null) // ate achar uma celula vazia,
		{ // achou a chave?
			if (hashArray[hashVal].getKey() == key) {
				DataItem temp = hashArray[hashVal]; // salva item
				hashArray[hashVal] = nonItem; // deleta item
				return temp; // retorna o item
			}
			++hashVal; // vai pra proxima celula
			hashVal %= arraySize; // volta pro comeco caso precise
		}
		return null; // nao achou o item :(
	} 

	public DataItem find(int key) // acha o item dando uma key
	{
		int hashVal = hashFunc(key); // hasheia a chave

		while (hashArray[hashVal] != null) // ata achar celula vazia,
		{ // achou a chave?
			if (hashArray[hashVal].getKey() == key)
				return hashArray[hashVal]; // Sim! retorna o cara
			++hashVal; // vai pra proxima celula
			hashVal %= arraySize; // volta tudo caso precise
		}
		return null; // nao achou o cara :(
	}
	
	/*
	 
	 private void binInsert(int key, int hashVal, DataItem item, int keyAux) {
		System.out.println("uepa");
		int i = nivel;
		
		//if (nivel != 0) {
		//	binInsert(key, hashVal, item, nivel);
		//}
		
		if (hashArray[hashVal] == null || hashArray[hashVal].getKey() == -1) { // espaco vazio
			hashArray[hashVal] = item; // insere item
			return;
		}
		int hashValCont = hashFuncCont(key) + hashVal;
		hashValCont %= arraySize;
		int hashValMove = hashFuncCont(hashArray[hashVal].getKey()) + hashVal;
		hashValMove %= arraySize;
		if (hashArray[hashValCont] == null || hashArray[hashValCont].getKey() == -1) { // esquerda vazio?
			//vazio, insere
			hashArray[hashValCont] = item;
			return;
		} else if (hashArray[hashValMove] == null || hashArray[hashValMove].getKey() == -1) { // direita vazio?
			//vazio, insere
			hashArray[hashValMove] = item;
			return;
		} else {
			//rootKeys.add(key);
			//rootKeys.add(hashArray[hashValMove].getKey());
			//hashValKeys.add();
			++nivel;
			binInsert(key, hashValCont, item, nivel);
			return;
		}
	}
	 
	 */
}